package com.yuan.leetcode.JianZhiOffer;

import java.util.LinkedList;

/**
 * Created by yuanhaowu
 * Time 2022/6/12 20:13
 *
 * 请完成一个函数，输入一个二叉树，该函数输出它的镜像。
 *
 * 输入：root = [4,2,7,1,3,6,9]
 * 输出：[4,7,2,9,6,3,1]
 *
 * 例如输入：
 *      4
 *    /   \
 *   2     7
 *  / \   / \
 * 1   3 6   9
 *
 * 镜像输出：
 *
 *      4
 *    /   \
 *   7     2
 *  / \   / \
 * 9   6 3   1
 */
public class offer27 {
    public TreeNode mirrorTree(TreeNode root) {
        if(root ==null){
            return null;
        }
        TreeNode tmp = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(tmp);
        return root;
    }

    //使用迭代（使用栈或队列皆可），更好理解
    //看方法二：https://leetcode.cn/problems/er-cha-shu-de-jing-xiang-lcof/solution/mian-shi-ti-27-er-cha-shu-de-jing-xiang-di-gui-fu-/
    public TreeNode mirrorTree2(TreeNode root){
        if(root == null){
            return null;
        }
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.add(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.poll();
            if(node.left!=null){
                stack.push(node.left);
            }
            if(node.right!=null){
                stack.push(node.right);
            }
            //交换结点
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return root;
    }
}
